package com.LeeCode;

import java.util.HashMap;

/**
 * 数位和相等数对的最大和
 */

public class Code2342 {
    public static void main(String[] args) {
        int[] nums = {18, 43, 36, 13, 7};
        System.out.println(new Code2342().maximumSum(nums));
    }

    public int maximumSum(int[] nums) {
        int ans = -1;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int maxNum = 0, temp = nums[i];
            while (temp != 0) {
                maxNum += temp % 10;
                temp = temp / 10;
            }

            if (map.containsKey(maxNum)) {
                temp = map.get(maxNum);
                ans = Math.max(ans, temp + nums[i]);
            }
            map.put(maxNum, Math.max(temp, nums[i]));
        }
        return ans;
    }

    public int maximumSum1(int[] nums) {
        int ans = -1;
        int[] mx = new int[82]; // 至多 9 个 9 相加
        for (int num : nums) {
            int s = 0; // num 的数位和
            for (int x = num; x > 0; x /= 10) { // 枚举 num 的每个数位
                s += x % 10;
            }
            if (mx[s] > 0) { // 说明左边也有数位和等于 s 的元素
                ans = Math.max(ans, mx[s] + num); // 更新答案的最大值
            }
            mx[s] = Math.max(mx[s], num); // 维护数位和等于 s 的最大元素
        }
        return ans;
    }

}
